package com.cn.codebrush.数组;

/**
 * @Author Boolean
 * @Date 2022/5/15 15:32
 * @Version 1.0
 */
public class No812最大三角形面积 {
    public static void main(String[] args) {
        int[][]  points = {{0,0},{0,1},{1,0},{0,2},{2,0}};
        System.out.println(largestTriangleArea(points));
    }

    /** 1. 转成梯形求三角形面试
     * 我们把 A(x1, y1),B(x2, y2),C(x3, y3)A(x1,y1),B(x2,y2),C(x3,y3)分别向 xx 轴投影，分别得到点E, D, FE,D,F。
     * 可以得到 3 个梯形：以下图中的黄色的边为梯形的上下底，分别以三角形的三条边作为梯形的斜边。
     * 于是：
     * 三角形 ABC 的面积 = 梯形 BDEA 的面积 + 梯形 AEFC 的面积 - 梯形 BDFC 的面积三角形ABC的面积=梯形BDEA的面积+梯形AEFC的面积−梯形BDFC的面积
     * = [(y1 + y2) * (x1 - x2)]/2 + [(y3 + y1) * (x3 - x1)]/2 - [(y2 + y3) * (x3 - x2)]/2
     * = [(y1+y2)∗(x1−x2)]/2+[(y3+y1)∗(x3−x1)]/2−[(y2+y3)∗(x3−x2)]/2
     * = 1/2 * [x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)]
     * = 1/2∗[x1(y2−y3)+x2(y3−y1)+x3(y1−y2)]
     * 我们就有了根据三角形的三点的坐标求面积的公式。
     *
     * 2. 海伦公式
     */
    public static double largestTriangleArea(int[][] points) {
        int N = points.length;
        double res = 0;
        for(int i=0;i<N-2;i++){
            for(int j=i+1;j<N-1;j++){
                for(int k=j+1;k<N;k++){
                    int x1 = points[i][0]; int y1 = points[i][1];
                    int x2 = points[j][0]; int y2 = points[j][1];
                    int x3 = points[k][0]; int y3 = points[k][1];

                    res = Math.max(res, 0.5 * Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)));
                }
            }
        }

        return res;
    }
}
